package lk;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class D230919 {
    // 盛最多水的容器
    // 首尾反向双指针
    // 时间复杂度: O(n)
    // 空间复杂度: O(1)
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int max = 0;
        while (left != right) {
            // 记录当前较小边
            int minHeight = Math.min(height[left], height[right]);
            // 计算当前容量
            int tmp = (right - left) * minHeight;
            // 更新最大容量
            max = Math.max(max, tmp);
            // 较小的一边, 向内移动, 直到大于当前记录的较小边
            while (left != right && height[left] <= minHeight) {
                left++;
            }
            while (left != right && height[right] <= minHeight) {
                right--;
            }
        }
        return max;
    }


    // K 和数对的最大数目
    // 将数组升序排序, 再使用双指针遍历数组
    // 时间复杂度: O(nlogn)
    // 空间复杂度: O(1)
    public int maxOperations(int[] nums, int k) {
        // 排序
        Arrays.sort(nums);
        // 双指针遍历数组, 寻找两个数相加等于 k
        int left = 0;
        int right = nums.length - 1;
        int count = 0;
        while (left < right) {
            int tmp = nums[left] + nums[right];
            if (tmp == k) {
                count++;
                left++;
                right--;
            } else if (tmp > k) {
                right--;
            } else {
                left++;
            }
        }
        return count;
    }


    // 子数组最大平均数 I
    // 定长滑动窗口
    // 时间复杂度: O(n)
    // 空间复杂度: O(1)
    public double findMaxAverage(int[] nums, int k) {
        int left = 0;
        int right = 0;
        int max = 0;
        int sum = 0;
        // 窗口大小是固定的, 先计算出第一个窗口的 和
        for (; right < k; right++) {
            sum += nums[right];
        }
        max = sum;

        // 窗口向右移动, 计算 最大和
        while (right < nums.length) {
            sum -= nums[left++];
            sum += nums[right++];
            max = Math.max(max, sum);
        }
        // 返回最大和的平均值
        return max * 1.0 / k;
    }



    // 定长子串中元音的最大数目
    // 定长滑动窗口
    // 时间复杂度: O(n)
    // 空间复杂度: O(1)
    private String vowel = "aeiou";
    public int maxVowels(String s, int k) {
        char[] arr = s.toCharArray();
        int left = 0;
        int right = 0;
        int count = 0;
        int max = 0;
        while (right < k) {
            count = vowel.indexOf(arr[right++]) != -1 ? count + 1 : count;
        }
        max = count;

        while (right < arr.length) {
            count = vowel.indexOf(arr[left++]) != -1 ? count - 1 : count;
            count = vowel.indexOf(arr[right++]) != -1 ? count + 1 : count;
            max = Math.max(max, count);
        }
        return max;
    }

    public static void main(String[] args) {
        // List<Parent> list = new ArrayList<Child>(); // 报错
        List<? extends Parent> list = new ArrayList<>(); // 正确
        List<? super Child> list1 = new ArrayList<Child>(); // 正确
        List<? super Child> list2 = new ArrayList<Parent>(); // 正确
    }
}

class Parent {

}
class Child extends Parent {

}